package com.leecode.xiehf.page_02;

import com.leecode.Printer;

import java.util.Stack;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * <p>
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * <p>
 *  
 * <p>
 * <p>
 * <p>
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 * <p>
 *  
 * <p>
 * <p>
 * <p>
 * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
 * <p>
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0084 extends Printer {

    public static void main(String[] args) {
        Solution_0084 solution = new Solution_0084();
        int[] num1 = new int[]{
                2, 1, 4, 5, 1, 3, 3
        };
        int s = solution.largestRectangleArea(num1);
        print(s);
    }

    public int largestRectangleArea(int[] heights) {
        int res = 0;
        // 穷举法
        int length = heights.length;
        int[] newHeights = new int[length+2];
        newHeights[0]=0;
        newHeights[length+1]=0;
        for (int i = 1; i < length+1; i++) {
            newHeights[i]=heights[i-1];
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length+2; i++) {
            while (!stack.isEmpty() && newHeights[i]<newHeights[stack.peek()]){
                int cur  = stack.pop();
                int height = newHeights[cur];
                int left = stack.peek();
                int width = i - left - 1;
                res = Math.max(width * height, res);
            }
            stack.push(i);
        }
        return res;
    }
}
